/**
 * 面试题14：剪绳子
 */
public class Offer_14 {
    /**
     * 数学（LeetCode官方）
     */
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        // 商
        int quotient = n / 3;
        // 余数
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) (Math.pow(3, quotient - 1) * 4);
        } else {
            return (int) (Math.pow(3, quotient) * 2);
        }
    }

    /**
     * 动态规划（LeetCode官方）
     */
    public int cuttingRope2(int n) {
        // dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积
        // 0 和 1 都不能拆分，因此 dp[0] = dp[1] = 0
        int[] dp = new int[n + 1];
        // 当 i >= 2 时，假设对正整数 i 拆分出的第一个正整数是 j（1<=j<i），则有以下两种方案：
        // 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j*(i−j)
        // 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j*dp[i-j]
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }

    /**
     * 动态规划-书上写法
     */
    public int cuttingRope1(int n) {
        if (n < 2) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= i / 2; j++) {
                int temp = dp[j] * dp[i - j];
                if (temp > max) {
                    max = temp;
                }
                dp[i] = max;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Offer_14 solution = new Offer_14();
        int ans = solution.cuttingRope(10);
        System.out.println(ans);
    }
}
